import java.util.*;

class AllOne {
    class Node{
        Node prev;
        Node next;
        Set<String> set;
        int count;
        public Node(){
            this("",0);
        }
        public Node(String key,int count){
            this.count=count;
            set=new HashSet<>();
            set.add(key);
        }

        public Node insert(Node node){
            node.prev=this;
            node.next=this.next;
            node.prev.next=node;
            node.next.prev=node;
            return node;
        }

        public void remove(){
            this.prev.next=this.next;
            this.next.prev=this.prev;
        }
    }

    Node root;
    Map<String,Node> map;
    /** Initialize your data structure here. */
    public AllOne() {
        root=new Node();
        root.prev=root;
        root.next=root;
        map=new HashMap<>();
    }

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    public void inc(String key) {
        if(map.containsKey(key)){
            Node cur=map.get(key);
            Node next=cur.next;
            if(next==root||next.count>cur.count+1){
                map.put(key,cur.insert(new Node(key,cur.count+1)));
            }else{
                next.set.add(key);
                map.put(key,next);
            }
            cur.set.remove(key);
            if(cur.set.isEmpty()){
                cur.remove();
            }
        }else{
            if(root.next==root||root.next.count>1){
                map.put(key,root.insert(new Node(key,1)));
            }else{
                root.next.set.add(key);
                map.put(key,root.next);
            }
        }
    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        Node cur=map.get(key);
        if(cur.count==1){
            map.remove(key);
        }else{
            Node prev= cur.prev;
            if(prev==root||prev.count<cur.count-1){
                map.put(key,cur.prev.insert(new Node(key, cur.count-1)));
            }else{
                prev.set.add(key);
                map.put(key,prev);
            }
        }
        cur.set.remove(key);
        if(cur.set.isEmpty()){
            cur.remove();
        }
    }

    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        return root.prev!=null?root.prev.set.iterator().next():"";
    }

    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
        return root.next!=null?root.next.set.iterator().next():"";
    }
}












public class project {
    public String minRemoveToMakeValid(String s) {
        Set<Integer> set=new HashSet<>();
        Stack<Integer> stack=new Stack<>();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                stack.add(i);
            }else if(s.charAt(i)==')'){
                if(stack.isEmpty()){
                    set.add(i);
                }else{
                    stack.pop();
                }
            }
        }
        while (!stack.isEmpty()){
            set.add(stack.pop());
        }
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<s.length();i++){
            if(!set.contains(i)){
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}



